package homework01;

public class LoopNumber {
	public static void main(String[] args){
		int cnt=0;
		int[] num,tmp;
		num = new int[1000];
		tmp = new int[1000];
		for (int i = 1; i <= 9; i++)
			for (int j = 0; j <= 9; j++)
				for(int k = 0; k <= 9; k++)
					num[++cnt] = i*10001+j*1010+k*100;

		msort(num,tmp,1,cnt);
		for (int i = 1; i <= cnt; i++)
			System.out.println(num[i]);
	}
	
	public static void msort(int[] num, int[] tmp, int le, int ri) {
		if (le == ri) return;
		int mid = (le + ri) / 2;
		msort(num,tmp,le, mid);
		msort(num,tmp,mid + 1,ri);
		int i = le, j = mid + 1, k = le;
		
		while (i <= mid && j <= ri){
			if (num[i]<=num[j]) {
				tmp[k]=num[i];
				i++;k++;
			}
			else {
				tmp[k]=num[j];
				j++;k++;
			}
		}
		
		while (i <= mid){
			tmp[k]=num[i];
			i++;k++;
		}
		while (j <= ri){
			tmp[k]=num[j];
			j++;k++;
		}
		
		for (int r = le; r <= ri; r++)
			num[r] = tmp[r];
	}
}


